David silver 强化学习 Lecture 3

课程主页： https://www.davidsilver.uk/teaching/

这里回顾David silver 强化学习 Lecture 3的课程内容，这一讲简单介绍了通过动态规划进行控制。

介绍

DP的要求

动态规划用于解决满足以下条件的问题：

• 最优子结构
• 重叠子问题

而MDP同时满足以上两个特性。

通过DP规划

• DP假设有MDP的完全信息
• DP用于MDP的规划
• 对于预测：
  • 输入：MDP $\langle\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma\rangle$和策略$\pi$
  • 或：MRP $\left\langle\mathcal{S}, \mathcal{P}^{\pi}, \mathcal{R}^{\pi}, \gamma\right\rangle$
  • 输出：价值函数$v_\pi$
• 对于控制：
  • 输入：MDP $\langle\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma\rangle$
  • 输出：最有价值函数$v_\star$
  • 以及：最优策略$\pi_\star$

策略评估

迭代策略评估

利用贝尔曼方程可以计算价值函数：

$$\begin{aligned} v_{k+1}(s) &=\sum_{a \in \mathcal{A}} \pi(a | s)\left(\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime} }^{a}v_k\left(s^{\prime}\right)\right) \\ v^{k+1} &=\mathcal{R}^{\pi}+\gamma \mathcal{P}^{\pi} v^{k} \end{aligned}$$

注意上述情形对应同步更新（synchronous），与之对应的是异步更新（asynchronous）。

策略迭代

• 给定策略$\pi$

  • 评估策略$\pi$

    $$v_{\pi}(s)=\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+\ldots | S_{t}=s\right]$$

  • 关于$v_\pi$提升策略

    $$\pi^{\prime}=\operatorname{greedy}\left(v_{\pi}\right)$$

上述过程被称为策略迭代，通常该策略会收敛到$\pi^\star$，上述过程可以用下图表示：

策略提升

• 考虑确定性策略$a=\pi(s)$

• 我们可以通过贪心的方式提升策略

  $$\pi^{\prime}(s)=\underset{a \in \mathcal{A}}{\operatorname{argmax}} q_{\pi}(s, a)$$

• 这一步就可以提升任何状态$s$的价值，

  $$q_{\pi}\left(s, \pi^{\prime}(s)\right)=\max _{a \in \mathcal{A}} q_{\pi}(s, a) \geq q_{\pi}(s, \pi(s))=v_{\pi}(s)$$

• 因此也提升了价值函数，$V_{\pi^{\prime}}(s) \geq V_{\pi}(s)$

  $$\begin{aligned} v_{\pi}(s) & \leq q_{\pi}\left(s, \pi^{\prime}(s)\right)=\mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) | S_{t}=s\right] \\ & \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma q_{\pi}\left(S_{t+1}, \pi^{\prime}\left(S_{t+1}\right)\right) | S_{t}=s\right] \\ & \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} q_{\pi}\left(S_{t+2}, \pi^{\prime}\left(S_{t+2}\right)\right) | S_{t}=s\right] \\ & \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma R_{t+2}+\ldots | S_{t}=s\right]=v_{\pi^{\prime}}(s) \end{aligned}$$

• 如果上述提升停止，那么

  $$q_{\pi}\left(s, \pi^{\prime}(s)\right)=\max _{a \in \mathcal{A}} q_{\pi}(s, a)=q_{\pi}(s, \pi(s))=v_{\pi}(s)$$

• 即贝尔曼最优方程得到满足

  $$v_{\pi}(s)=\max _{a \in \mathcal{A}} q_{\pi}(s, a)$$

• 因此对于所有$s\in \mathcal S$，我们有$v_{\pi}(s)=v_{*}(s)$

• 即$\pi$是最优策略

价值迭代

最优准则

任何最优策略可以被划分为两个部分：

• 最优的第一步动作$A_\star$
• 后继状态$S’$的最优策略

定理（最优准则）

策略$\pi (a|s)$从状态$s$得到最优价值，$v_{\pi}(s)=v_{*}(s)$，当且仅当

• 对于任何从$s$处可达的状态$s’$
• $\pi$达到状态$s’$的最优价值，$v_{\pi}\left(s^{\prime}\right)=v_{*}\left(s^{\prime}\right)$

确定性价值迭代

• 如果我们已知子问题的解$v_\star(s’)$

• 那么解$v_\star(s)$可以通过一步向前看求解

  $$v_{\star}(s) \leftarrow \max _{a \in \mathcal{A}} \mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} v_{\star}\left(s^{\prime}\right)$$

价值迭代

$$\begin{aligned} v_{k+1}(s) &=\max _{a \in \mathcal{A}}\left(\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S} \atop v_{k}} \mathcal{P}_{s s^{\prime}}^{a} v_{k}\left(s^{\prime}\right)\right) \\ v_{k+1} &=\max _{a \in \mathcal{A}} \mathcal{R}^{a}+\gamma \mathcal{P}^{a} v_{k} \end{aligned}$$

DP扩展

之前介绍的DP都是同步DP，实际中还有异步DP，有如下三个思想实现异步DP：

• In-place DP
• Prioritised sweeping
• Real-time DP

In-place DP

• 同步值迭代使用的方法是：

  $$\begin{aligned} v_{\text{new}}(s) &\leftarrow \max _{a \in \mathcal{A}}\left(\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} v_{\text{old}}\left(s^{\prime}\right)\right)\\ v_{\text{new}}& \leftarrow v_{\text{old}} \end{aligned}$$

• In-place值迭代使用的方法是：

  $$v(s) \leftarrow \max _{a \in \mathcal{A}}\left(\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} v\left(s^{\prime}\right)\right)$$

Prioritised sweeping

• 使用贝尔曼误差来指导状态的选择，例如

  $$\left|\max _{a \in \mathcal{A}}\left(\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} v\left(s^{\prime}\right)\right)-v(s)\right|$$

• 备份Bellman剩余误差最大的状态

• 每次备份后更新受影响状态的Bellman误差

Real-time DP

• 思想：只有状态和智能体相关

• 使用智能体的经验指导状态的选择

• 在每个时间戳$S_{t}, A_{t}, R_{t+1}$

• 备份状态$S_t$

  $$v\left(S_{t}\right) \leftarrow \max _{a \in \mathcal{A}}\left(\mathcal{R}_{S_{t}}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s_{t} s^{\prime}}^{a} v\left(s^{\prime}\right)\right)$$

压缩映像

这部分讨论策略迭代和价值迭代的收敛性问题，首先定义范数：

$$\|u-v\|_{\infty}=\max _{s \in \mathcal{S}}|u(s)-v(s)|$$

• 定义贝尔曼期望备份算子$T^\pi$，

  $$T^{\pi}(v)=\mathcal{R}^{\pi}+\gamma \mathcal{P}^{\pi} v$$

• 那么$T^\pi$是$\gamma$压缩的，

  $$\begin{aligned}\left\|T^{\pi}(u)-T^{\pi}(v)\right\|_{\infty} &=\left\|\left(\mathcal{R}^{\pi}+\gamma \mathcal{P}^{\pi} u\right)-\left(\mathcal{R}^{\pi}+\gamma \mathcal{P}^{\pi} v\right)\right\|_{\infty} \\ &=\left\|\gamma \mathcal{P}^{\pi}(u-v)\right\|_{\infty} \\ & \leq\left\|\gamma \mathcal{P}^{\pi}\right\| u-v\left\|_{\infty}\right\|_{\infty} \\ & \leq \gamma\|u-v\|_{\infty} \end{aligned}$$

这里给出如下定理：

定理（压缩映像定理）

对于任意完备度量空间$\mathcal V$，考虑定义在其上的$\gamma$-压缩算子$T(v)$：

• $T$收敛到唯一的固定点
• 收敛速度和$\gamma$呈线性关系

上述定理说明贝尔曼期望算子$T^{\pi}$存在不动点，即$v_\pi$。